/* 

给你一个整数数组 nums ，设计算法来打乱一个没有重复元素的数组。

实现 Solution class:

Solution(int[] nums) 使用整数数组 nums 初始化对象
int[] reset() 重设数组到它的初始状态并返回
int[] shuffle() 返回数组随机打乱后的结果
 

示例：

输入
["Solution", "shuffle", "reset", "shuffle"]
[[[1, 2, 3]], [], [], []]
输出
[null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]

解释
Solution solution = new Solution([1, 2, 3]);
solution.shuffle();    // 打乱数组 [1,2,3] 并返回结果。任何 [1,2,3]的排列返回的概率应该相同。例如，返回 [3, 1, 2]
solution.reset();      // 重设数组到它的初始状态 [1, 2, 3] 。返回 [1, 2, 3]
solution.shuffle();    // 随机返回数组 [1, 2, 3] 打乱后的结果。例如，返回 [1, 3, 2]
 

提示：

1 <= nums.length <= 200
-106 <= nums[i] <= 106
nums 中的所有元素都是 唯一的
最多可以调用 5 * 104 次 reset 和 shuffle

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shuffle-an-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

*/

// Fisher-Yates 洗牌算法 
// 题解：https://leetcode-cn.com/problems/shuffle-an-array/solution/xi-pai-suan-fa-by-xing-guang-29/
// Fisher-Yates 洗牌算法 
// 思路:
// 我们可以用一个简单的技巧来降低之前算法的时间复杂度和空间复杂度，那就是让数组中的元素互相交换，这样就可以避免掉每次迭代中用于修改列表的时间了。
//
// 算法:
// Fisher-Yates 洗牌算法跟暴力算法很像。在每次迭代中，生成一个范围在当前下标到数组末尾元素下标之间的随机整数。
// 接下来，将当前元素和随机选出的下标所指的元素互相交换 - 这一步模拟了每次从 “帽子” 里面摸一个元素的过程，
// 其中选取下标范围的依据在于每个被摸出的元素都不可能再被摸出来了。此外还有一个需要注意的细节，
// 当前元素是可以和它本身互相交换的 - 否则生成最后的排列组合的概率就不对了。
var Solution = function (nums) {
    this.nums = nums;
};

// 获取原数组
Solution.prototype.reset = function () {
    return this.nums;
};

// 打乱数组
Solution.prototype.shuffle = function () {
    const nums = this.nums.slice(0);
    const n = nums.length;

    // 产生的结果有 n! 种可能
    for (let i = 0; i < n; i++) {
        // 从 i 到 n-1 随机选一个
        const rand = randOne(i, n - 1);
        // 交换nums数组i和rand下标的两个元素
        [nums[i], nums[rand]] = [nums[rand], nums[i]];
    }

    return nums;
};

// 获取闭区间 [n, m] 内的一个随机整数
function randOne(n, m) {
    return Math.floor(Math.random() * (m - n + 1)) + n;
};